1. Field of the Invention
The present invention generally relates to a method and apparatus for integer linear programming, and more particularly to a method and apparatus for generating a profile of solutions that trades off a number of activities utilized against an objective value for a bilinear integer optimization model. The bilinear integer optimization model seeks to determine the activities (encoded by integers) and the integer utilizations of these activities, so as to minimize the objective value. For clarity, the exemplary method (and system) is developed and discussed in an exemplary case of a cutting stock problem. In this case, a profile of solutions is generated to trade off the number of patterns used to cut raw units of stock material while minimizing the amount of material wasted.
2. Description of the Related Art
When attempting to solve a specific problem, it is desirable to provide a profile of possible solutions as opposed to generating a single possible solution for the problem. This idea will be illustrated in the present application using the exemplary “cutting stock problem”. In the cutting stock problem, a user has a supply of stock rolls. The stock rolls may include any stock material that may be available in discrete units including, but not limited to, paper, chemical fiber, film, steel, wire and cable, wood, etc. The material in stock rolls has a width of Wmax. A certain number, di of stock rolls are demanded of material with width wi (where i=1, 2, . . . , m; and wi<Wmax). The user desires to cut up the stock rolls to satisfy the demand while minimizing the amount of trim loss created.
There are several additional restrictions, which must be considered when handling the cutting stock problem. For instance, Wmin is a lower bound on the allowed nominal trim loss per stock roll. Additionally, the cutting machines used to cut the stock material have a limited number of knives, which limits the type of patterns that may be utilized. Furthermore, widths of material up to a threshold ω are considered to be “narrow”, and there is a limit on the number (Cnar) of “narrows” permitted to be cut from a stock roll of material.
It is disadvantageous to provide the user with a single solution to the cutting stock problem, or any other problem. It is desirable to provide a profile of solutions that trades off a minimization of an objective of the problem against a number of activities utilized in the solution. In the case of the cutting stock problem, it is desirable to provide a profile of solutions that trades off the amount of trim loss created against the number of distinct cutting patterns used. In the cutting stock problem, it is important to limit the number of distinct cutting patterns, because there is a changeover cost associated with setting up the stock cutting machine to cut a different pattern.
Several column generation approaches are conventionally used for generating solutions to a proposed problem. One such approach is the Gilmore and Gomory method (e.g., see Paul C Gilmore and Ralph E. Gomory, “A Linear Programming Approach to the Cutting-Stock Problem”, Operations Research, 9:849-859, 1961). In the Gilmore and Gomory method constraints involving coverage of given demand using a known set of activities are treated in a master problem. Constraints describing feasible activities are treated in a subproblem.
The Gilmore and Gomory approach seeks a linear-programming solution at the master problem level. Thus, necessary information is communicated to the subproblem by prices (i.e., dual variables). Since the user desires an integer solution to the master problem, prices are not sufficient to describe the optimal coverage of demand based on known activities to the subproblem.
The above shortcoming of the conventional column-generating methods is overcome by “branching”. A common branching method is the Branch-and-Price method (e.g., see Gleb Belov and Guntram Scheithauer, “The Number of Setups (Different Patterns) in One-Dimensional Stock Cutting”, 2003, Preprint, Dresden University, Institute for Numerical Mathematics). This method requires substantial computational resources as it emphasizes proving the optimality of a solution, as opposed to finding a good approximate solution. Moreover, this method does not lend itself to efficiently providing a profile of solutions with the desired tradeoff. The Branch-and-Price method tends to provide good solutions, but because of the substantial computational requirements, can be a very slow process. On the other hand, the Gilmore and Gomory process is a fast process, but may not provide good overall solutions.